﻿/*
** Xin YUAN, 2022, BSD (2)
*/

////////////////////////////////////////////////////////////////////////////////
#ifndef __CTL_MATCH_H__
#define __CTL_MATCH_H__
////////////////////////////////////////////////////////////////////////////////

#ifndef __CTL_DEF_H__
	#error match.h requires def.h to be included first.
#endif

////////////////////////////////////////////////////////////////////////////////
namespace CTL {
////////////////////////////////////////////////////////////////////////////////

//------------------------------------------------------------------------------
// KMP

/*
Each element of pNext indicates the next position of pMatch based on 1
while mismatch.
If tis value is 0, the position of source string should be moved to the next position,
and the position of pMatch should be set to 1 (based on 1).
*/

template <typename T, class TCompareTrait = DefaultCompareTrait<T>>
inline void KMP_CalcNext(const T* pMatch, uintptr_t uLength, uintptr_t* pNext) noexcept
{
	assert( uLength > 0 );

	uintptr_t j, k;
	j = 0;  // 1 - 1
	k = 0;
	pNext[0] = 0;  //next[1] = 0  next[1 - 1]

	while ( j < uLength - 1 ) { // j < uLength (if j is based on 1)
		if ( k == 0 || TCompareTrait::IsEQ(pMatch[j], pMatch[k - 1]) ) { // t[j] t[k] -- t[k - 1]
			++ j;
			++ k;
			if ( TCompareTrait::IsEQ(pMatch[j], pMatch[k - 1]) ) // t[j] t[k] -- t[k - 1]
				pNext[j] = pNext[k - 1];  //next[j] = next[k]
			else
				pNext[j] = k;  //next[j] = k
		}
		else {
			k = pNext[k - 1];  //k = next[k] -- next[k - 1]
		}
	}
}

template <typename T, class TCompareTrait = DefaultCompareTrait<T>>
class KMP_Matcher
{
public:
	KMP_Matcher() noexcept : m_pMatch(NULL), m_uMatchLen(0), m_pNext(NULL)
	{
	}
	KMP_Matcher(const KMP_Matcher&) = delete;
	KMP_Matcher& operator=(const KMP_Matcher&) = delete;
	~KMP_Matcher() noexcept
	{
		dump();
	}

	void Initialize(const T* pMatch, uintptr_t uLen)
	{
		assert( pMatch != NULL && uLen > 0 );
		dump();
		m_pNext = (uintptr_t*)AllocatorTraits::Allocate(uLen * sizeof(uintptr_t));
		if ( m_pNext == NULL )
			ExceptionTraits::ThrowMemory();  //throw
		KMP_CalcNext<T, TCompareTrait>(pMatch, uLen, m_pNext);
		m_pMatch = pMatch;
		m_uMatchLen = uLen;
	}

	const T* GetPointer() const noexcept
	{
		return m_pMatch;
	}
	uintptr_t GetLength() const noexcept
	{
		return m_uMatchLen;
	}
	const uintptr_t* GetNextPointer() const noexcept
	{
		return m_pNext;
	}
	uintptr_t GetNext(uintptr_t index) const noexcept
	{
		assert( index < GetLength() );
		return m_pNext[index];
	}

private:
	void dump() noexcept
	{
		if ( m_pNext != NULL ) {
			AllocatorTraits::Free(m_pNext);
			m_pNext = NULL;
		}
	}

private:
	const T*    m_pMatch;
	uintptr_t   m_uMatchLen;
	uintptr_t*  m_pNext;
};

/*! \brief A structure for match information.

A structure for match information.
*/
struct MatchInfo
{
	uintptr_t  uSrcPos;    //!< Specify the position in source data block.
	uintptr_t  uMatchPos;  //!< Specify the position in match block.
	bool       bMatched;   //!< Specify whether the match block is matched.
};

template <typename T, class TCompareTrait = DefaultCompareTrait<T>>
class KMP_Searcher
{
public:
	KMP_Searcher() noexcept : m_pSrc(NULL), m_uSrcLen(0), m_pMatcher(NULL),
			m_uSrcPos(0), m_uMatchPos(0)
	{
	}
	KMP_Searcher(const KMP_Searcher&) = delete;
	KMP_Searcher& operator=(const KMP_Searcher&) = delete;
	~KMP_Searcher() noexcept
	{
	}

	void Initialize(const T* pSrc, uintptr_t uLen, const KMP_Matcher<T, TCompareTrait>* pMatcher) noexcept
	{
		assert( pMatcher != NULL );
		assert( pMatcher->GetNextPointer() != NULL );
		assert( uLen == 0 || (uLen > 0 && pSrc != NULL) );
		m_pSrc = pSrc;
		m_uSrcLen = uLen;
		m_pMatcher = pMatcher;
		m_uSrcPos = 0;
		m_uMatchPos = 1;
	}

	//called repeatedly
	bool Find(MatchInfo& info) noexcept
	{
		assert( m_pMatcher != NULL );
		assert( m_pMatcher->GetNextPointer() != NULL );
		if ( m_uSrcPos >= m_uSrcLen )
			return false;
		const T* pMatch = m_pMatcher->GetPointer();
		const uintptr_t* pNext = m_pMatcher->GetNextPointer();
		uintptr_t uMatchLen = m_pMatcher->GetLength();
		while ( m_uSrcPos < m_uSrcLen && m_uMatchPos <= uMatchLen ) {
			if ( m_uMatchPos == 0
				|| TCompareTrait::IsEQ(m_pSrc[m_uSrcPos], pMatch[m_uMatchPos - 1]) //s[i] t[j]
				) {
				m_uSrcPos ++;
				m_uMatchPos ++;
			}
			else {
				info.uSrcPos = m_uSrcPos;
				info.uMatchPos = m_uMatchPos - 1;
				info.bMatched = false;
				m_uMatchPos = pNext[m_uMatchPos - 1];  //j = next[j]
				return true;
			}
		}
		info.uSrcPos = m_uSrcPos;
		info.uMatchPos = m_uMatchPos - 1;
		if ( m_uMatchPos > uMatchLen ) { // m_uMatchPos will not overflow
			info.bMatched = true;
			m_uMatchPos = 1;
			return true;
		}
		info.bMatched = false;
		return true;
	}

private:
	const T*   m_pSrc;
	uintptr_t  m_uSrcLen;

	const KMP_Matcher<T, TCompareTrait>*  m_pMatcher;

	uintptr_t  m_uSrcPos;
	uintptr_t  m_uMatchPos;  //based on 1
};

/*! \brief Find a sequence in a source data block.

Find a sequence in a source data block.
\tparam T The element type.
\tparam TCompareTrait The compare trait of element.
\param pSrc [in] A pointer to source data block.
\param uLen [in] The length of source data block.
\param pMatcher [in] A pointer to match block.
\return 0 means failure, otherwise means the index in pSrc based on 1.
*/
template <typename T, class TCompareTrait = DefaultCompareTrait<T>>
inline uintptr_t KMP_Find(const T* pSrc, uintptr_t uLen, const KMP_Matcher<T, TCompareTrait>* pMatcher) noexcept
{
	KMP_Searcher<T, TCompareTrait> searcher;
	searcher.Initialize(pSrc, uLen, pMatcher);
	if ( uLen < pMatcher->GetLength() )
		return 0;
	MatchInfo info;
	while ( searcher.Find(info) ) {
		if ( info.bMatched )
			return info.uSrcPos - info.uMatchPos + 1;  //i - tlen
	}
	return 0;
}

//------------------------------------------------------------------------------
//Sunday Match Algorithm

class SundayMatcher
{
public:
	SundayMatcher() noexcept : m_pMatch(nullptr), m_uMatchLen(0), m_bCaseIgnore(false)
	{
	}
	SundayMatcher(const SundayMatcher&) = delete;
	~SundayMatcher() noexcept
	{
	}

	SundayMatcher& operator=(const SundayMatcher&) = delete;

	void Initialize(const uint8_t* pMatch, uintptr_t uMatchLen, bool bCaseIgnore) noexcept
	{
		assert( pMatch != nullptr && uMatchLen > 0 );
		m_pMatch = pMatch;
		m_uMatchLen = uMatchLen;
		m_bCaseIgnore = bCaseIgnore;
		MemoryTraits::Zero(m_move_table, sizeof(m_move_table));
		for ( uintptr_t i = uMatchLen; i > 0; i -- ) {
			uint8_t ch = pMatch[i - 1];
			if ( bCaseIgnore )
				ch = (uint8_t)CharTraits<char>::ToLower((int8_t)ch);
			if ( m_move_table[ch] == 0 )
				m_move_table[ch] = uMatchLen - i + 1;
		}
	}

	const uint8_t* GetPointer() const noexcept
	{
		return m_pMatch;
	}
	uintptr_t GetLength() const noexcept
	{
		return m_uMatchLen;
	}
	bool IsCaseIgnore() const noexcept
	{
		return m_bCaseIgnore;
	}

	uintptr_t GetMove(uint8_t ch) const noexcept
	{
		if ( m_bCaseIgnore )
			ch = (uint8_t)CharTraits<char>::ToLower((int8_t)ch);
		return m_move_table[ch];
	}

private:
	const uint8_t* m_pMatch;
	uintptr_t m_uMatchLen;
	uintptr_t m_move_table[256];
	bool m_bCaseIgnore;
};

//Sunday_Find
/*! \brief Find a sequence in a data block.

Find a sequence in a data block.
\param pSrc [in] A pointer to source data.
\param uLen [in] The length of source data.
\param matcher [in] Specify the match block.
\return 0 means failure, otherwise means the index in pSrc based on 1.
*/
inline uintptr_t Sunday_Find(const uint8_t* pSrc, uintptr_t uLen, const SundayMatcher& matcher) noexcept
{
	assert( uLen == 0 || (pSrc != nullptr && uLen > 0) );
	uintptr_t uSrcPos = 0;
	const uint8_t* pMatch = matcher.GetPointer();
	uintptr_t uMatchLen = matcher.GetLength();
	bool bCaseIgnore = matcher.IsCaseIgnore();
	uintptr_t uMove = 0;
	while ( uLen - uSrcPos >= uMatchLen ) {
		uint8_t ch, ch1;
		bool bSame = true;
		uintptr_t uBound = uMove == 0 ? 0 : uMatchLen - uMove + 1;
		//last N
		for ( uintptr_t i = uMatchLen; i > uBound; i -- ) {
			ch = pSrc[uSrcPos + i - 1];
			if ( bCaseIgnore )
				ch = (uint8_t)CharTraits<char>::ToLower((int8_t)ch);
			ch1 = pMatch[i - 1];
			if ( bCaseIgnore )
				ch1 = (uint8_t)CharTraits<char>::ToLower((int8_t)ch1);
			if ( ch != ch1 ) {
				bSame = false;
				break;
			}
		}
		if ( bSame ) {
			uBound = uMove == 0 ? 0 : uMatchLen - uMove;
			//first N
			for ( uintptr_t i = 0; i < uBound; i ++ ) {
				ch = pSrc[uSrcPos + i];
				if ( bCaseIgnore )
					ch = (uint8_t)CharTraits<char>::ToLower((int8_t)ch);
				ch1 = pMatch[i];
				if ( bCaseIgnore )
					ch1 = (uint8_t)CharTraits<char>::ToLower((int8_t)ch1);
				if ( ch != ch1 ) {
					bSame = false;
					break;
				}
			}
		}
		if ( bSame )
			return uSrcPos + 1;  //found
		if ( uLen - uSrcPos == uMatchLen )
			break;
		//move
		uMove = matcher.GetMove(pSrc[uSrcPos + uMatchLen]);
		if ( uMove == 0 )
			uSrcPos += (uMatchLen + 1);
		else
			uSrcPos += uMove;
	}
	return 0;
}

////////////////////////////////////////////////////////////////////////////////
}
////////////////////////////////////////////////////////////////////////////////
#endif
////////////////////////////////////////////////////////////////////////////////
